package com.lz.tree.rb;

import java.util.LinkedList;
import java.util.Queue;

public class RedBlackTree1 {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    public static class Node<T> {
        T value;
        Node<T> left, right;
        boolean color; // 节点颜色
        int layer; //层

        Node(T value) {
            this.value = value;
            this.left = this.right = null;
            this.color = RED; // 新插入的节点默认是红色
        }

        public int getLayer() {
            return layer;
        }

        public void setLayer(int layer) {
            this.layer = layer;
        }
    }

    public Node<String> insert(Node<String> node, String value) {
        if (node == null) return new Node<>(value);

        int cmp = value.compareTo(node.value);
        if (cmp < 0) node.left = insert(node.left, value);
        else if (cmp > 0) node.right = insert(node.right, value);
        else node.value = value; // 如果值相同，则更新值

        // 插入后的修复操作
        if (isRed(node.right) && !isRed(node.left)) node = rotateLeft(node);
        if (isRed(node.left) && isRed(node.left.left)) node = rotateRight(node);
        if (isRed(node.left) && isRed(node.right)) flipColors(node);

        return node;
    }

    private boolean isRed(Node<String> node) {
        if (node == null) return false;
        return node.color == RED;
    }

    private Node<String> rotateLeft(Node<String> h) {
        Node<String> x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        return x;
    }

    private Node<String> rotateRight(Node<String> h) {
        Node<String> x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        return x;
    }

    private void flipColors(Node<String> h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    // 测试代码
    public static void main(String[] args) {
        RedBlackTree1 tree = new RedBlackTree1();
        Node<String> root = null;
        root = tree.insert(root, "3");
        root = tree.insert(root, "2");
        root = tree.insert(root, "8");
        root = tree.insert(root, "5");
        root = tree.insert(root, "9");
        root = tree.insert(root, "4");

        Node<String> firstNode = root;
        Queue<Node<String>> queue = new LinkedList<>();
        queue.offer(firstNode);
        while (!queue.isEmpty()) {
            Node<String> currentNode = queue.poll();
            System.out.println(currentNode.value);
            if (currentNode.left != null) {
                queue.offer(currentNode.left);
            }
            if (currentNode.right != null) {
                queue.offer(currentNode.right);
            }
        }

    }
}
